
/*
回溯
连接：https://leetcode.cn/problems/letter-case-permutation/description/
题目：784. 字母大小写全排列
算法思路：
我们需要在每⼀个位置上考虑所有的可能情况并且不能出现重复。通过深度优先搜索的⽅式，不断地
枚举每个数在当前位置的可能性，并回溯到上⼀个状态，直到枚举完所有可能性，得到正确的结果。
我们需要定义⼀个变量 ⽤来记录所有可能的排列数量，⼀个⼀维数组 visited 标记元素，然后从第⼀个
位置开始进⾏递归；
递归函数设计：void backtrack(int index, int &n)
参数：index（当前需要处理的位置）；
返回值：⽆；
函数作⽤：在当前位置填⼊⼀个合理的数字，查找所有满⾜条件的排列。
递归流程如下：
1. 递归结束条件：当 index 等于 n 时，说明已经处理完了所有数字，将当前数组存⼊结果中；
2. 在每个递归状态中，枚举所有下标 x，若这个下标未被标记，并且满⾜题⽬条件之⼀：
a. 将 visited[x] 标记为 1；
b. 对第 index+1 个位置进⾏递归；
c. 将 visited[x] 重新赋值为 0，表⽰回溯


   减枝：选过的数不能选
        不满足优美数组条件的不能选
*/
class Solution {
public:
    int ret;
    bool check[16] = {false};
    int countArrangement(int n) {
        dfs(1,n);
        return ret;
    }
    void dfs(int pos,int n)//pos从1开始
    {
        if(pos==n+1)
        {
            ret++;
            return ;
        }
        for(int i =1;i<=n;i++)
        {
            if(check[i]==false && (i%pos==0 || pos%i==0))
            {
                check[i] = true;
                dfs(pos+1,n);
                check[i] = false;
            }
        }
    }
};